//相当于优化的插入排序
public class ShellSort {
    public static void shell(int[] array){
        int gap= array.length/2;
        while(gap>=1){
            shellSort(array,gap);
            gap/=2;
        }
    }

    private static void shellSort(int[] array,int gap) {
        for (int i = gap; i < array.length; i++) {
            int j=i;
            while(j-gap>=0&&array[j]>=array[j-gap]){
                swap(array,j,j-gap);
                j-=gap;
            }

        }

    }
    public static void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
    public static void main(String[] args) {
        int[] arr={9,8,7,6,5,4,10,3,2,1};
        shell(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

}
